package Algorithms.chapter2_1;

public class MaxPQ<Key extends Comparable<Key>> {
    //构建元素靠不断插入
    private Key[] pq; //完全二叉树
    private int N = 0;
    public MaxPQ(int maxN){
        pq=(Key[]) new Comparable[maxN+1]; //创建对象
    }
    public boolean isEmpty(){
        return N==0;
    }
    public int size(){
        return N;
    }
    public void insert(Key v){
        pq[++N]=v;
        swim(N);
    }
    public Key delMax(){
        //获取根结点最大值，与最后一个交换位置以后消失，新上位的赶快下沉。
        Key max=pq[1];
        exch(1,N--);
        pq[N+1]=null;
        sink(1);
        return max;
    }
    private boolean less(int i,int j){
        return pq[i].compareTo(pq[j])<0;//字符串比较的方法
    }
    private void exch(int i,int j){
        Key t=pq[i];pq[i]=pq[j];pq[j]=t;
    }
    private void swim(int k){
        //上浮,选中K元素,如果大于根界点那么上浮
        while (k>1&&less(k/2,k)){
            exch(k/2,k);
            k=k/2;
        }
    }
    private void sink(int k){
        //下沉
        while(2*k<=N){
            int j =2*k;
            if(j<N&&less(j,j+1)) j++;
            if(!less(k,j)) break;
            exch(k,j);
            k=j;


        }
    }




}
